/**
 * 1145. 二叉树着色游戏
 * https://leetcode-cn.com/problems/binary-tree-coloring-game/
 */
public class Solutions_1145 {
    public static void main(String[] args) {
        String str = "[1 2 3 4 5 6 7 8 9 10 11]";
//        int n = 11, x = 3;  // output: true   选择 1 节点，即 3 的父节点
//        int n = 11, x = 1;  // output: true   选择 2 节点，即 1 的左子节点
        int n = 11, x = 2;  // output: false   选择 2 的左子节点、右子节点、父节点，都无法获胜

        TreeNode root = MyTreeNodeUtils.deserialize(str);
        boolean result = btreeGameWinningMove(root, n, x);
        System.out.println(result);
    }

    /**
     * n = 11，x = 3 时，存在贪心思想
     * 计算得到三个方向的数量
     *      x 的左子树节点数量 leftCnt：1
     *      x 的右子树节点数量 rightCnt：1
     *      除 x 及其子树外，其他节点的数量：n - 1 - leftCnt - rightCnt
     * y 要想获胜，可以选三个方向，即 x 的父节点（如果有），x 的左子节点，x 的右子节点
     * 三个方向上，有任意一方的节点数量大于 n / 2，那么 y 就可以获胜（因为目前是 y 选，可以选最优的方向），否则 y 失败
     */
    public static boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        if (root == null) {
            return false;
        }
        // dfs 找到 x 节点
        if (root.val == x) {
            // 计算左、右子节点数量
            int leftRes = getCount(root.left);
            int rightRes = getCount(root.right);
            // 计算除 x 及其子树外，其他节点的数量
            int parentRes = n - leftRes - rightRes - 1;
            // 要想获胜，必须染色 winCount + 1 个节点
            int winCount = n / 2;
            if (leftRes > winCount || rightRes > winCount || parentRes > winCount) {
                // y 获胜
                return true;
            }
        }
        return btreeGameWinningMove(root.left, n, x) ||
                btreeGameWinningMove(root.right, n, x);
    }

    /**
     * 获取节点数量
     */
    public static int getCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getCount(root.left) + getCount(root.right) + 1;
    }
}
